// 超级回文数
// 如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。
// 现在，给定两个正整数 L 和 R （以字符串形式表示），
// 返回包含在范围 [L, R] 中的超级回文数的数目。
// 1 <= len(L) <= 18
// 1 <= len(R) <= 18
// L 和 R 是表示 [1, 10^18) 范围的整数的字符串
//测试链接 : https://leetcode.cn/problems/super-palindromes/
public class SuperPalindromes1 {
    public int superpalindromesInRange(String left, String right) {
        long l = Long.valueOf(left);  //转化成long类型
        long r = Long.valueOf(right);

        //查找的数最大只用到根号r范围
        long limit = (long) Math.sqrt(r);

        int ans = 0; //记录答案
        long num = 0; //表示根号r的值
        long seed = 1; //设置种子
        do{
            num = evenNumber(seed);  //生成偶数的回文数
            if(check(num, l, r)){
                ans++;
            }

            num = oddNumber(seed);  //生成奇数的回文数
            if(check(num,l,r)){
                ans++;
            }
            seed++;
        }while(num <= limit);

        return ans;
    }


    public long evenNumber(long seed){
        long ans = seed;
        while(seed > 0){
            ans = ans * 10 + seed % 10;
            seed /= 10;
        }
        return ans;
    }

    public long oddNumber(long seed){
        long ans = seed;
        seed /= 10;
        while(seed > 0){
            ans = ans * 10 + seed % 10;
            seed /= 10;
        }
        return ans;
    }


    public boolean check(long num, long l, long r) {
        //判断范围
        long ret = num * num;
        if(ret < l || ret > r){
            return false;
        }

        //判断ret是否是回文数
        return isPalindrome(ret);
    }

    public boolean isPalindrome(long num){
        long offset = 1;
        while(num / offset >= 10){
            offset *= 10;
        }

        while(num != 0){
            //num首位判断是否一致
            if(num / offset != num % 10){
                return false;
            }
            num = ( num % offset ) / 10;
            offset /= 100;
        }

        return true;
    }
}
